package flare.analytics.graph
{
  import flare.animate.Transitioner;
  import flare.util.Property;
  import flare.vis.data.Data;
  import flare.vis.data.DataList;
  import flare.vis.data.NodeSprite;
  import flare.vis.operator.Operator;

  /**
   * Calculates betweenness centrality measures for nodes in a graph.
   * The algorithm used is due to Ulrik Brandes, as published in the
   * <a href="http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf">
   * Journal of Mathematical Sociology, 25(2):163-177, 2001</a>.
   */
  public class BetweennessCentrality extends Operator
  {
    private var _bc:Property = Property.$("props.centrality");

    /** The property in which to store the centrality score. This property
     *  is used to annotate nodes with their betweenness centrality score.
     *  The default value is "props.centrality". */
    public function get centralityField():String
    {
      return _bc.name;
    }

    public function set centralityField(f:String):void
    {
      _bc = Property.$(f);
    }

    /** Flag indicating the type of links to follow in the graph. The
     *  default is <code>NodeSprite.GRAPH_LINKS</code>. */
    public var links:int = NodeSprite.GRAPH_LINKS;

    /**
     * Creates a new BetweennessCentrality operator.
     */
    public function BetweennessCentrality()
    {
    }

    /** @inheritDoc */
    public override function operate(t:Transitioner = null):void
    {
      calculate(visualization.data);
    }

    /**
     * Calculates the betweenness centrality values for the given data set. 
     * @param data the data set for which to compute centrality measures
     */
    public function calculate(data:Data):void
    {
      var nodes:DataList = data.nodes;
      var N:int = nodes.length, i:int;
      var n:NodeSprite, v:NodeSprite, w:NodeSprite;
      var si:Score, sv:Score, sw:Score;

      nodes.visit(function(n:NodeSprite):void
      {
        _bc.setValue(n, 0);
        n.props._score = new Score();
      });

      for(i = 0; i < N; ++i)
      {
        nodes.visit(function(n:NodeSprite):void
        {
          n.props._score.reset();
        });
        n = nodes[i];
        si = n.props._score;
        si.paths = 1;
        si.distance = 0;

        var stack:Array = [];
        var queue:Array = [n];

        while(queue.length > 0)
        {
          stack.push(v = queue.shift());
          si = v.props._score;

          v.visitNodes(function(w:NodeSprite):void
          {
            var sv:Score = si, sw:Score = w.props._score;

            if(sw.distance < 0)
            {
              queue.push(w);
              sw.distance = sv.distance + 1;
            }

            if(sw.distance == sv.distance + 1)
            {
              sw.paths += sv.paths;
              sw.predecessors.push(v);
            }
          }, links);
        }

        while(stack.length > 0)
        {
          w = stack.pop();
          sw = w.props._score;

          for each(v in sw.predecessors)
          {
            sv = v.props._score;
            sv.dependency += (sv.paths / sw.paths) * (1 + sw.dependency);
          }

          if(w !== n)sw.centrality += sw.dependency;
        }
      }

      nodes.visit(function(n:NodeSprite):void
      {
        _bc.setValue(n, n.props._score.centrality);
        delete n.props._score;
      });
    }
  } // end of class BetweennessCentrality
}

import flare.util.Arrays;

/** Helper class for storing intermediate centrality computations */
class Score
{
  public var dependency:Number = 0;
  public var distance:Number = - 1;
  public var paths:Number = 0;
  public var predecessors:Array = [];
  public var centrality:Number = 0;

  public function reset():void
  {
    Arrays.clear(predecessors);
    dependency = 0;
    distance = - 1;
    paths = 0;
  }
}